#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e7+7,M=11;
int n,m,k,mod,ans,fac[N],invf[N],r;
int inv[N],sw[N],dp[M][M],F[M],G[N],del[N];
int pw(int a,int b){
	int s=1;
	while(b){
		if(b&1)s=s*a%mod;
		a=a*a%mod,b>>=1;
	}return s;
}int C(int x,int y){
	if(x<y)return 0;
	return fac[x]*invf[y]%mod*invf[x-y]%mod;
}signed main(){
	freopen("sequence.in","r",stdin);
	freopen("sequence.out","w",stdout);
	cin>>n>>m>>k>>mod,fac[0]=1;
	for(int i=1;i<N;i++)fac[i]=fac[i-1]*i%mod;
	invf[N-1]=pw(fac[N-1],mod-2);
	for(int i=N-2;i>=0;i--)invf[i]=invf[i+1]*(i+1)%mod;
	for(int i=1;i<N;i++)inv[i]=fac[i-1]*invf[i]%mod;
	sw[n]=pw(n,mod-2);
	for(int i=n-1;i>=0;i--)sw[i]=sw[i+1]*n%mod;
	if(k==0){
		for(int i=0;i<=n;i++)ans=(ans+C(m+i-1,m-1)*C(n,i)%mod*fac[i]%mod*i%mod*sw[i]%mod)%mod;
		cout<<(ans%mod+mod)%mod<<"\n";
		return 0;
	}if(k>0){
		dp[0][0]=1;
		for(int i=0;i<=k;i++)
			for(int j=0;j<i;j++){
				dp[i][j]=(dp[i][j]+dp[i-1][j]*(j+1))%mod;
				if(j)dp[i][j]=(dp[i][j]+dp[i-1][j-1]*((i<<1)-1-j))%mod;
			}
		for(int i=0;i<k;i++)F[i]=dp[k][i];
		G[0]=1;
		for(int i=0;i<n-m;i++){
			for(int j=0;j<=min(i,k-1);j++)del[i]=(del[i]+F[j]*G[i-j])%mod;
			if(i)del[i]=(del[i]+del[i-1])%mod;
			r=1ll*del[i]*m%mod*((k<<1)+1)%mod;
			for(int j=max(i-k+2,0ll);j<=i;j++)r=(r+G[j]*F[i-j+1]%mod*(i-j+1)%mod*m%mod)%mod;
			for(int j=1;j<=min(i,k-1);j++)r=(r-F[j]*G[i-j+1]%mod*(i-j+1)%mod)%mod;
			G[i+1]=r*inv[i+1]%mod;
		}for(int i=m;i<=n;i++)ans=(ans+G[i-m]*C(n,i)%mod*fac[i]%mod*i%mod*sw[i]%mod)%mod;
		cout<<(ans%mod+mod)%mod<<"\n";
		return 0;
	}if(k<0){
        for(int i=1;i<=(-k);i++){
			F[i]=pw(i,i+k+mod-1);
			for(int j=1;j<i;j++)F[i]=(F[i]-F[j]*pw(i,i-j-1)%mod*j%mod*C(i,j)%mod)%mod;
		}
		for(int i=1;i<=(-k);++i)F[i]=F[i]*invf[i]%mod;
		G[0]=1;
		for(int i=0;i<n-m;i++){
			r=0;
			for(int j=max(i-(-k)+2,0ll);j<=i;j++)r=(r+G[j]*F[i-j+2]%mod*(i-j+1)%mod*m%mod)%mod;
			for(int j=1;j<=min(i,(-k)-1);j++)r=(r-F[j+1]*G[i-j+1]%mod*(i-j+1)%mod)%mod;
			G[i+1]=1ll*r*inv[i+1]%mod;
		}for(int i=m;i<=n;i++)ans=(ans+G[i-m]*C(n,i)%mod*fac[i]%mod*i%mod*sw[i]%mod)%mod;
		cout<<(ans%mod+mod)%mod<<"\n";
        return 0;
    }
	return 0;
}
